题解 P5834@洛谷 【[USACO19DEC]MooBuzz】

题目大意：求从一开始第$n$个既不是三的倍数又不是五的倍数的数

没有思路。列几个数看看：

1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 26, 28, 29, ……

因为三乘五等于十五，所以猜测模15的余数可能有规律。列一下：

1, 2, 4, 7, 8, 11, 13, 14, 1, 2, 4, 7, 8, 11, 13, 14, ……

于是很明显地发现存在8位的循环节。根据数学推导可得（以下所有公式中的除号“/”均表示整除，即向下取整）：

$ans=(n/8)*15+a[n\mod8]$，其中$a[1...n]=\{14, 1, 2, 4, 7, 8, 11, 13\}$，就是上面推导的余数。

但是当$n\mod8=0$时发现有问题，此时$ans=(n/8)*15-1$，特判一下就好。

AC代码：

#include <bits/stdc++.h>
using namespace std;

int a[8] = {14, 1, 2, 4, 7, 8, 11, 13};

int main()
{
	int n;
    cin>>n;
    int d = n / 8;
    int ans = d * 15;
    if(n % 8 != 0) ans += a[n%8];
    else --ans;
    cout<<ans<<endl;
    return 0;
}